Autonomous vehicles may be equipped with many sensors that allow the vehicles to perceive other vehicles, obstacles, and pedestrians in the environment. Moreover, the autonomous vehicles can use information about perceived features in the environment to localize the vehicle. That is, the autonomous vehicle can correlate perceived features (e.g., road markings, terrain, etc.) with mapped features to determine a position within the environment. Accordingly, a static feature-based map that includes position information for the mapped features can be used as a basis for comparison to perform the localization. However, as aspects of an environment change from construction or other causes, the changes can cause difficulties with localizing the vehicle according to the feature map.